1. Field of the Invention
The invention relates to genetic algorithm techniques and applications.
2. Description of Related Art
Genetic algorithms evolve solutions to problems using properties of natural selection. Generally, a genetic algorithm starts with a population of attempted solutions to a problem, evaluates the attempted solutions, and uses the better solutions as the basis of a next generation of attempted solutions. Typically, the process continues until some satisfactory solution emerges. Genetic algorithms have produced solutions for a wide variety of problems such as numerical optimization, circuit layout, and so forth.
As an example of a genetic algorithm, FIGS. 1-4 illustrate a genetic algorithm that “guesses” six randomly chosen numbers 100. FIG. 1 shows an initial population 110 of attempted solutions. The population includes individuals 104 A, B, C, and D. Each individual has an associated chromosome 106. Each chromosome 106 includes a series of genes. In the example shown, each gene represents a different guessed digit. In genetic algorithm terminology, the value of a particular gene is known as its “trait”; possible traits (e.g., digits 0 to 9) are known as “alleles”; and the position of a gene within a chromosome is known as its “locus.”
As shown in FIG. 1, some chromosomes 106 in the initial population came closer to guessing the solution 100 than others. A fitness measure 108 represents how closely each chromosome 106 came to the solution 100. In this case, the fitness measure 108 represents how many correct digits a chromosome 106 includes. For example, individual A, having a chromosome of “0 1 2 0 2 1”, has two correctly placed digits, underlined, of the solution sequence “1 1 2 1 0 0” 100 and, thus, has a fitness measure of “2”. Individual B shares three digits with the solution 100, and, thus, has a fitness measure 108 of “3”. None of the individuals, however, exactly match the solution 100.
To generate another generation of individuals, genetic algorithms commonly operate on existing individuals having better fitness measures. For example, a genetic algorithm can mutate genes of an existing individual.
FIG. 2 shows an example of mutation. As shown, a genetic algorithm has generated a new individual, E, by mutating the last gene of individual A from a “1” 114 to a “0” 116.
Genetic algorithms also commonly use a “crossover” operation to generate offspring. In crossover, parents exchange genetic material to create an offspring. For example, as shown in FIG. 3, two parents, B and C, generate offspring F by contributing the first four digits 118 of individual B and the last two digits 120 of individual C. Thus, the fifth gene represents a crossover point. Commonly, genetic algorithms randomly select one or more crossover points when generating offspring.
FIG. 4 shows the population 110 after the generation of offspring shown in FIGS. 2 and 3, and the elimination of chromosomes having the poorest fitness measures (i.e., individuals C and D in FIG. 1). The offspring shown, individuals E and F, have better fitness measures 108 than their parents. The average fitness measure for the population has also increased. While offspring sometime offer poorer fitness measures than their parent(s), repeated fitness based selection and offspring generation tends to increase the fitness measures of a population. The genetic algorithm may continue generating and measuring the fitness of chromosomes, for example, until a chromosome exactly matches the solution 100.